The present invention relates generally to chaotic communications systems and more particularly to a chaotic communication system utilizing a chaotic receiver estimation engine. This estimation engine both synchronizes and recovers data by mapping probability calculation results onto the chaotic dynamics via a strange attractor geometrical approximation. For synchronization, the system does not require either a stable/unstable subsystem separation or a chaotic system inversion. The techniques employed can be implemented with any chaotic system for which a suitable geometric model of the attractor can be found.
Chaos is an area of science and mathematics that is characterized by processes that are nonlinear, such as equations that have a squared or higher order term. Chaotic processes are iterative, in that they perform the same operations over and over. By taking the result of the process (equations) and performing the process again on the result, a new result is generated. Chaos is often called deterministically random motion. Chaotic processes are deterministic because they can be described by equations and because knowledge of the equations and a set of initial values allows all future values to be determined. Chaotic processes also appear random since a sequence of numbers generated by chaotic equations has the appearance of randomness. One unique aspect of chaos compared to an arbitrarily chosen aperiodic nonlinear process is that the chaotic process can be iterated an infinite number of times, with a result that continues to exist in the same range of values or the same region of space.
A chaotic system exists in a region of space called phase space. Points within the phase space fly away from each other with iterations of the chaotic process. Their trajetories are stretched apart but their trajectories are then folded back onto themselves into other local parts of the phase space but still occupy a confined region of phase space A geometrical shape, called the strange attractor, results from this stretching and folding process. One type of strange attractor for a chaotic process called the Rossler system is depicted in FIG. 1, and illustrates the stretching and folding process. The chaotic attracter exists in perpetuity in the region of phase space for which the chaotic system is stable.
In an unstable system, two points in phase space that are initially close together become separated by the stretching and the folding, which causes the points to be placed correspondingly farther apart in the phase space than they originally were. Repeating the process (iterating) accentuates the situation. The points not only diverge from each other, but both trajectories move toward infinity and, therefore, away from the stable region of perpetual chaotic existence.
The sequences of points that result from two closely spaced initial conditions become very different very quickly in chaotic processes. The Henon chaotic system, for example, has been shown to start with two initial conditions differring by one (1) digit in the 15th decimal place. The result was that within 70 iterates the trajectories were so different that subtracting them resulted in a signal that was as large as the original trajectories"" signals themselves. Therefore, the stretching and folding causes the chaotic process to exhibit sensitive dependence on initial conditions. A receiver without perfect information about a transmitter (a xe2x80x9ckeyxe2x80x9d) will be unable to lock to the transmitter and recover the message. Even if a very close lock were achieved at one point in time, it is lost extremely quickly because the time sequences in the transmitter and receiver diverge from each other within a few iterations of the chaotic process.
Chaotic nonlinear dynamics may be utilized in telecommunications systems. There is interest in utilizing and exploiting the nonlinearities to realize secure communications, while achieving reductions in complexity, size, cost, and power requirements over the current communications techniques. Chaotic processes are inherently spread in frequency, secure in that they possess a low probability of detection and a low probability of intercept, and are immune to most of the conventional detection, intercept, and disruption methods used against current xe2x80x98securexe2x80x99 communications systems based on linear pseudorandom noise sequence generators. Chaotic time sequences theoretically never repeat, making them important for such applications as cryptographic methods and direct sequence spread spectrum spreading codes. In addition, chaotic behavior has been found to occur naturally in semiconductors, feedback circuits, lasers, and devices operating in compression outside their linear region.
Unfortunately, many of these characteristics also complicate the task of recovering the message in the chaotic transmission. A fundamental problem permeating chaotic communications research is the need for synchronization of chaotic systems and/or probabilistic estimation of chaotic state, without which there can be no transfer of information. Without synchronization, meaning alignment of a local receiver chaotic signal or sequence with that of the transmitter, the characteristic of sensitive dependence on initial conditions causes free-running chaotic oscillators or maps to quickly diverge from each other, preventing the transfer of information. Probability-based estimates of chaotic state are typically made via correlation or autocorrelation calculations, which are time consuming. The number of iterates per bit can be reasonable in conjunction with synchronization, but values of several thousand iterates per bit are typically seen without synchronization.
A general communications system employing chaos usually consists of a message m(t) injected into a chaotic transmitter, resulting in a chaotic, encoded transmit signal y(t). This signal is altered as it passes through the channel, becoming the received signal r(t). The receiver implements some mix of chaotic and/or statistical methods to generate an estimate of the message me(t).
The recovery of a message from transmitted data depends on the ability of the receiver to perform either asynchronous or synchronous detection. There are three fundamental approaches to chaotic synchronization delineated in the literature of the prior art: (1) decomposition into subsystems, (2) inverse system approach, and (3) linear feedback.
If the approach is a decomposition into subsystems, the chaotic system is divided into two or more parts: an unstable subsystem usually containing a nonlinearity and one or more stable subsystems. The stable subsystem may contain a nonlinearity if its Lyapunov exponents remain negative. The Lyapunov exponents of all subsystems must be computed to evaluate the stability or instability of each one, where negative Lyapunov exponents indicate stability and positive Lyapunov exponents indicate instability. The arbitrary division into stable and unstable systems is accomplished by trial and error until successful. The driver or master system is the complete chaotic system, and the driven or slave system(s) consists of the stable subsystem(s). In general, synchronization will depend on circuit component choices and initial conditions.
The problem with using the decomposition approach is threefold. First, the decomposition into subsystems is arbitrary, with success being defined via the results of Lyapunov exponent calculations. There is presently no known method by which to synthesize successful subsystem decomposition to satisfy a set of requirements. Second, the evaluation of Lyapunov exponents can become extremely involved, complicated, and messy. The time and effort spent evaluating a trial, arbitrary decomposition can be extensive, with no guarantee of success. Third, there can be several possible situations for the subsystem decompositions for a given chaotic process. A chaotic process could have single acceptable decomposition, multiple acceptable decompositions, or no acceptable decompositions. Since the method is by trial-and-error and without guarantee of success, a general approach that will work for an arbitrary chaotic process is highly desirable.
In the inverse system approach, the receiver is designed to invert the chaotic function of the transmitter. For appropriate choices of transmitter systems and initial conditions, inverse systems can be designed into a receiver that results in perfect recovery of a noiseless transmitted message. However, one major drawback of using the inverse system approach is that signal noise results in erroneous message recovery. In addition, the invertible system must be based on a specially designed chaotic process since generic chaotic signals are not invertible. The collection of specially designed invertible chaotic processes is very small. This seriously limits the repertoire of receiver designs as well as the library of applicable chaotic process choices. Hostile countermeasures designers would have a relatively easy time analyzing and compromising the small set of systems that could be developed using these invertible chaotic functions.
In the linear feedback system approach, a master-slave setup is used in which the output of the slave system is fed back and subtracted from the received chaotic time sequence to generate an error function. The error function drives the slave system in a manner reminiscent of a phase-lock loop. Synchronization depends on the initial conditions of the master and slave systems. One drawback of linear feedback systems is that without a set of constraints on the initial conditions, synchronization of the master and slave systems cannot be guaranteed. In addition, the slave is a stable subsystem of the chaotic process, and is subject to the same drawbacks and limitations enumerated for the subsystem decomposition method above.
In addition to the three fundamental approaches to chaotic synchronization, there are four basic methods of encoding digital data into chaotic transmitted sequences: masking, orbit control, chaos shift key, and orthogonal autocorrelation sequence. They employ several different chaotic systems, with the most commonly mentioned including the Henon, Rossler, Lorenz, and Double Scroll (Chua""s circuit). Most of these methods have variations in their implementations. A common problem among them is the issue of transmitter-receiver synchronization.
Signal masking refers to the process of embedding a message in a free-running chaotic time series such that the message is hidden, the chaotic dynamics are not altered enough to preclude synchronization, and the chaotic noise-like waveform is the dominant transmit feature. Signal masking consists of the message signal being added to a chaotic signal and recovered via subtraction of the synchronized receiver local chaotic signal from the received waveform. The masking signal requirements are satisfied when the message power has an embedding factor on the order of xe2x88x9230 dBc, which places the message power 30 dB below the chaotic power. Synchronization has been shown at higher information signal power levels, but with increased incidence of synchronization error bursts and degraded message recovery. One difficulty with this method is that noise power on the order of the message signal power level results in erroneous message recovery. The transmit SNR, which is determined by the power of the chaotic signal, must be very large in order to overcome the effects of modest channel noise which wastes power and broadcasts the signal presence (non-LPD). In addition, small trajectory perturbations, as little as the order of 10xe2x88x9216, can result in significant synchronization error bursts. Another difficulty for real implementations is that most synchronous chaotic systems can""t accommodate channel losses, because the receiver synchronization degrades when the received signal has been attenuated from its original transmitted value. Finally, an unintended listener can recover the message without knowledge of the chaotic system by performing a mathematical reconstruction of the chaotic attractor and using it in conjunction with a set of recent observations to make local predictions of the immediate future for the chaotic system. Sufficiently accurate results are obtained to subtract out the chaotic process and uncover the hidden message, thereby compromising the security of the chaotic communication.
Chaotic attractors consist of an infinite number of unstable periodic orbits, all of which will be approached eventually from any initial condition. The system trajectory will be repelled away from any given orbit because of the stretching and folding of the chaotic dynamics, but it will eventually return to within a small neighborhood of the same orbit for the same reason. Orbit control exploits this type of behavior to transmit information by controlling the system trajectory such that it stays in the vicinity of one or more orbits for a prescribed length of time or follows a predetermined sequence of orbits. This method is very sensitive to noise and relatively small perturbations to the transmitted signal can cause the receiver trajectory to drift out of the required orbit.
Using the chaos shift key method of encoding digital data into chaotic transmitted sequences, for a binary-valued data stream, an aspect of the chaotic system is altered to create a transmit data stream. One method is to toggle a chaotic system parameter value, causing the data stream to switch between two chaotic attractors. Alternatively, the output can be inverted or not (i.e., multiplied by +1 or xe2x88x921), causing the two attractors to be mirror images of each other. Both methods utilize a chaotic synchronization scheme as a precondition of message recovery. The message is demodulated either via the detection of synchronization with one of two attractors in the receiver (a hardware version of which is used with a Chua""s circuit), or by the statistical method of correlation between the received sequence and a local chaotic signal over a large number of samples.
The orthogonal autocorrelation sequence method of encoding digital data into chaotic transmitted sequences develops a system with signal properties such that multiple user signals can be combined at the transmitter and then separated at each receiver by an autocorrelation calculation. The technique is presented as a general design method independent of the chaotic system used for the transmitter, but heavy use is made of a specific chaotic process in developing the concepts and results. Reasons for developing this scheme include the claims that non-repeating chaotic carrier signals provide greater transmission security than periodic carriers, require neither acquisition nor tracking logic for successful detection, and are more immune to co-channel interference than periodic carrier methods. Implementation investigations have demonstrated that an extremely large number of received values is required to accomplish demodulation, severely restricting the message data rates.
The present invention is a communications system based on a chaotic estimation engine. The invention provides for efficient communication with as little as two iterates per bit, a very general synchronization scheme, the integration of statistical methods with chaotic dynamics in the data recovery calculations, algorithms to enable a maximum aposteriori transmitted value estimation, secure communication by using completely overlapping ranges of transmit values for the conveyance of a logical zero or a logical one, and the development of a signal-to-noise ratio (SNR) estimator that produces good estimates of the true channel SNR and tracks changes in the channel noise power over time.
A transmit sequence is derived that sends one version of the chaotic strange attractor for a logical one and another version for a logical zero. Several new computational techniques allow for the estimation of both the instantaneous and average signal-to-noise ratio (SNR) values, as well as the maximum a posteriori (MAP) transmitted value for a given received chaotic iterate.
The receiver synchronizes to the transmitted chaotic sequence without requiring a chaotic equation separation into stable and unstable components or the design of an invertible chaotic process as was done in previous systems. The two processes of chaotic synchronization and message recovery required for synchronous communications are interleaved in the receiver estimation engine algorithms, obviating the need for an independent effort to achieve the synchronization of the transmitted chaotic signal with a locally generated version in the receiver. The estimation engine has the ability to make accurate decisions with as little as two chaotic iterations per data bit.
Three different estimates are generated for each received value and then combined into a single initial decision. This initial decision is mapped onto the closest portion of the geometric structures used to model the chaotic attractors via a minimum Euclidean metric. This mapping results in the final receiver decision of the transmitted value for the current received iterate. The concluding step of combining the decisions for all iterates in a bit yields the receiver bit decision, which is the transmitted message recovery.
A nonlinear chaotic receiver comprises a component for receiving a chaotic encoded digital signal transmission from a chaotic transmitter, synchronizing the chaotic receiver with the chaotic transmitter and recovering the contents of the encoded chaotic digital signal transmission using a chaotic strange attractor model and a chaotic probability density function model. Synchronization of the chaotic receiver with the chaotic transmitter and recovery of the contents of the encoded chaotic digital signal transmission may occur in the same calculations and result concurrently from the same calculations. The chaotic encoded digital signal transmission is a data sequence comprising a first through N number of iterates, wherein the first iterate represents a first value in the data sequence and the Nth iterate represents a last value in the data sequence. The chaotic strange attractor model comprises using one chaotic sequence to represent a logical zero data state and using a second chaotic sequence to represent a logical one data state. The first and second chaotic sequences may have attractors with completely overlapping regions of validity and the attractors may be mirror images of each other. The attractors are modeled as a set of geometrical functions having defined regions of validity. The chaotic strange attractor model comprises a strange attractor generated by combining Henon and mirrored Henon attractors, wherein the Henon and mirrored Henon attractors are generated by starting with one or more arbitrary points within an area of phase space that stretches and folds back onto itself, and inputting the points to a set of Henon equations, the result being the Henon attractor, and taking a mirror image of the Henon attractor to form the mirrored Henon attractor where the strange attractor is represented as a set of parabolas displayed on a Cartesian coordinate system and the parabolic regions of validity of the strange attractor are determined. The chaotic attractor model determines any existing fixed point on the strange attractor that repeats itself through multiple iterations of the chaotic transmission. The data sequence of the received chaotic encoded digital signal transmission is randomly selected from the group consisting of a first logical state for the Henon attractor and a second logical state for the mirrored Henon attractor. The chaotic probability density function models the probability of the first and second logical states of the Henon and mirrored Henon attractors as a random selection. The Henon strange attractor is generated by using image calculations on a Henon map, is represented in a Cartesian coordinate system as a crescent-like shape which occupies all four quadrants of the Cartesian coordinate system and is modeled as a set of four parabolas. The contents of the encoded chaotic digital signal transmission is determined by generating an initial decision for the contents of each iterate and generating a final decision for the contents of each iterate using a decision and weighting function. The final decision is generated using a synchronizer and final decision function and the final decision is used to recover the data sequence. The contents of the encoded chaotic digital signal transmission are determined by generating three estimates for each iterate received and calculating an initial decision for each iterate and mapping the initial decision onto the chaotic attractor to form a final decision for each estimate. The three estimates comprise a first estimate which is the value of the received iterate, a second estimate which is a minimum error probabilistic estimate and a third estimate which is a final decision of the previous iterate processed through Henon and mirrored Henon equations. The three estimates are combined to form the initial decision through a weighted average using probability calculations for the first, second and third estimates.
A means for determining a synchronization estimate to synchronize the chaotic receiver with a chaotic transmitter that generates the encoded chaotic digital signal transmission is provided. Signal estimates of the value of the 1 through N iterates received are generated.
The signal estimates comprise a received value which is equal to the actual value of the received iterate, a maximum a posteriori (MAP) estimate and a decision feedback estimate. The decision feedback estimate comprises generating a first decision feedback estimate for iterate n by passing iterate (nxe2x88x921) through Henon equations and generating a second decision feedback estimate for iterate n by passing iterate (nxe2x88x921) through mirrored Henon equations.
The decision and weighting function comprises performing a probabilistic combination of the three signal estimates by finding a probability for each iterate for each received value, MAP estimate and decision feedback estimate, generating an initial decision for each iterate, selecting the feedback estimate closest in value to the received value and the MAP estimate, generating weighting factors used in a weighted average computation and performing a weighted average, calculating a discount factor to discount a final decision for received values close to zero, determining the Cartesian coordinate representation of the initial decision and passing the Cartesian coordinates of the initial decision to a synchronizer and final decision generator and passing the zero proximity discount value to a system to bit map function. The weighting factors comprise generating a first weighting factor that quantifies channel effects by using a transmit PDF window used in determining the MAP estimate and multiplying the channel effects weighting factor by a second weighting factor that uses a PDF selected from the group consisting of the received PDF and transmit PDF, the result being the weighting factor for each iterate which is passed to the synchronization and final decision function. A discount weight is calculated to reduce the impact of initial decisions whose receive values are close to zero.
The selection of the feedback estimate comprises calculating one dimensional Euclidean distances from the received value and MAP estimate to the first and second feedback estimates and selecting the feedback estimate with the minimum Euclidean distance.
The synchronization and final decision function uses an initial decision from the decision and weighting function and maps Cartesian coordinates of the initial decision onto a Cartesian coordinate representation of the strange attractor. The mapping comprises inputting the initial decision into parabola models, the parabola models comprising equations approximating Henon and mirrored Henon attractors and calculating two dimensional Euclidean distance between the initial decision and every point on all parabolas and selecting a point on an attractor model corresponding to a minimum Euclidean distance as the final decision of the value of each iterate. The transmitted data sequence is recovered by combining the final decision of iterates 1 through N to determine the encoded digital signal transmission data sequence.
The nonlinear chaotic receiver comprises a receiver estimation engine for synchronizing the chaotic receiver with a chaotic transmitter and recovering the value of an encoded chaotic digital signal transmission. The receiver estimation engine comprises a signal-to-noise ratio (SNR) estimator, a maximum a posteriori (MAP) estimator, a feedback estimator wherein the chaotic receiver and the chaotic transmitter synchronization and the encoded digital signal transmission recovery occur concurrently while executing the same set of calculations within the receiver estimation engine. The receiver also includes a decision and weighting function within the receiver estimation engine comprising determining the probability of the estimate produced by the SNR estimator, the MAP estimator and the feedback estimator for each received iterate. The receiver calculates an initial decision for the iterate, a discount weight for a final decision for received values in close proximity to zero, and determines the final estimate of each iterate based on the initial decision from the decision and weighting function and then combines the final decision of iterates 1 through N to recover the encoded digital signal transmission data sequence.
The present invention comprises a method in a computer system and computer-readable instructions for controlling a computer system for receiving and recovering the contents of a chaotic encoded digital signal transmission by receiving a chaotic encoded digital signal transmission from a chaotic transmitter, synchronizing the chaotic receiver with the chaotic transmitter, and recovering the contents of the encoded chaotic digital signal transmission using a chaotic strange attractor model and a chaotic probability density function model.